package leetcode.editor.cn;

import java.util.*;
import leetcode.editor.common.*;

public class MergeIntervals {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[][] merge(int[][] intervals) {
            final LinkedList<int[]> res = new LinkedList<>();

            // 先排序  按照 array[0] 排序
            Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));

            // 取最大区间，应该是 右边尽可能 大，左边尽可能小
            // 先把最小边加上
            res.add(intervals[0]);

            // 依次向后找 ，看区间是否 可以合并（有交集）
            for (int i = 1; i < intervals.length; i++) {
                final int[] curr = intervals[i];
                //  res 中的最后一个元素的引用
                final int[] last = res.getLast();
                // 当前区间的 左，比上一区间的 右小，说明 有交集   [1,3]  ,  [2,4]
                if(curr[0]<=last[1]){
                    // 取两个区间的右侧，较大值
                    last[1]=Math.max(curr[1],last[1]);
                }else {
                    // 说明无交集，直接处理下一个区间
                    res.add(curr);
                }
            }
            // 题目要求输出 二维数组，所以需要转一下
            return res.toArray(new int[0][0]);
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    
    public static void main(String[] args) {
        Solution solution = new MergeIntervals().new Solution();
        // put your test code here
        final int[][] merge = solution.merge(new int[][]{{1, 3}, {2, 6}, {8, 10}, {15, 18}});
        System.out.println(merge);
    }
}
